\defmodule{RandomPermutation}

Provides methods to randomly shuffle arrays
or lists using a random stream.
% These methods shuffle the entire array.


\bigskip\hrule

\begin{code}
\begin{hide}
/*
 * Class:        RandomPermutation
 * Description:  Provides methods to randomly shuffle arrays or lists
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since

 * SSJ is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation, either version 3 of the License, or
 * any later version.

 * SSJ is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * A copy of the GNU General Public License is available at
   <a href="http://www.gnu.org/licenses">GPL licence site</a>.
 */
\end{hide}
package umontreal.iro.lecuyer.rng;\begin{hide}

import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
\end{hide}

public class RandomPermutation\begin{hide} {
   private static final int SHUFFLE_THRESHOLD = 5;
\end{hide}

   public static void init (byte[] array, int n)\begin{hide} {
      for (byte k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Initializes \texttt{array} with the first $n$
  positive integers in natural order as \texttt{array}$[i-1] = i$, for
  $i=1,...,n$.  The size of \texttt{array} must be at least $n$.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}

   public static void init (short[] array, int n)\begin{hide} {
      for (short k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{init}{}{\texttt{(byte[], int)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}

   public static void init (int[] array, int n)\begin{hide} {
      for (int k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{init}{}{\texttt{(byte[], int)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}

   public static void init (long[] array, int n)\begin{hide} {
      for (int k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{init}{}{\texttt{(byte[], int)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}

   public static void init (float[] array, int n)\begin{hide} {
      for (int k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{init}{}{\texttt{(byte[], int)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}

   public static void init (double[] array, int n)\begin{hide} {
      for (int k = 1; k <= n; k++)
         array[k-1] = k;
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{init}{}{\texttt{(byte[], int)}}.
\bigskip\hrule
\end{tabb}
\begin{htmlonly}
   \param{array}{the array to initialize.}
   \param{n}{number of elements initialized.}
\end{htmlonly}
\begin{code}
\begin{hide}@SuppressWarnings("unchecked")\end{hide}
   public static void shuffle (List<?> list, RandomStream stream)\begin{hide} {
      // The implementation is inspired from Sun's Collections.shuffle
      final int size = list.size ();
      if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
         for (int i = size; i > 1; i--)
            Collections.swap (list, i - 1, stream.nextInt (0, i - 1));

      } else {
         final Object arr[] = list.toArray ();

         // Shuffle array<
         shuffle (arr, stream);

         // Dump array back into list
         final ListIterator it = list.listIterator ();
         for (Object element : arr) {
            it.next ();
            it.set (element);
         }
      }
   }\end{hide}
\end{code}
\begin{tabb} Same as \texttt{java.util.Collections.shuffle(List<?>, Random)},
 but uses a \class{RandomStream} instead of \texttt{java.util.Random}.
\end{tabb}
\begin{htmlonly}
   \param{list}{the list being shuffled.}
   \param{stream}{the random stream used to generate integers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (Object[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final Object tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb}   Randomly permutes \texttt{array} using \texttt{stream}.
  This method permutes the whole array.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (byte[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final byte tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Randomly permutes \texttt{array} using \texttt{stream}.
  This method permutes the whole array.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (short[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final short tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (int[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final int tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (long[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final long tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (char[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final char tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (boolean[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final boolean tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (float[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final float tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (double[] array, RandomStream stream)\begin{hide} {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt (0, i);
         final double tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }\end{hide}
\end{code}
\begin{tabb}  Similar to \method{shuffle}{}{\texttt{(byte[], RandomStream)}}.
\bigskip\hrule
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}
\begin{hide}@SuppressWarnings("unchecked")\end{hide}
   public static void shuffle (List<?> list, int k, RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= size.

      // The implementation is inspired from Sun's Collections.shuffle
      final int size = list.size ();
      if (k < 0 || k > size)
         throw new IllegalArgumentException("k must be   0 <= k <= list.size()");
      if (0 == k) return;
      if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
         for (int i = 0; i < k; i++) {
            // Get random j in {i,...,n-1} and interchange a[i] with a[j].
            int j = stream.nextInt (i, size-1);
            Collections.swap (list, i, j);
         }

      } else {
         final Object arr[] = list.toArray ();

         // Shuffle array<
         shuffle (arr, size, k, stream);

         // Dump array back into list
         final ListIterator it = list.listIterator ();
         for (Object element : arr) {
            it.next ();
            it.set (element);
         }
      }
   }\end{hide}
\end{code}
\begin{tabb} Partially permutes \texttt{list} as follows using \texttt{stream}:
 draws the first $k$ new elements of \texttt{list} randomly among the $n$ old
 elements of \texttt{list}, assuming that $k \le n = $ \texttt{list.size()}.
 In other words, $k$ elements are selected at random without replacement from
 the $n$ \texttt{list} entries and are placed in the first $k$ positions,
 in random order.
\end{tabb}
\begin{htmlonly}
   \param{list}{the list being shuffled.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate integers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (Object[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      // Replace by 
      // if (k < 0 || k > n) throw new IllegalArgumentException();
      // or at least assert 0 <= k && k <= n;
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         Object temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb}  Partially permutes \texttt{array} as follows
 using \texttt{stream}: draws the new $k$ elements, \texttt{array[0]} to
 \texttt{array[k-1]}, randomly among the old $n$  elements, \texttt{array[0]}
 to \texttt{array[n-1]}, assuming that $k \le n \le$ \texttt{array.length}.
 In other words, $k$ elements are selected at random without replacement
 from the first $n$ array elements and are placed in the first 
 $k$ positions, in random order.
% Invoking shuffleArray (a, a.length, a.length, stream) randomly shuffles 
% the entire array.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (byte[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         byte temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (short[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         short temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (int[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         int temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (long[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         long temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (char[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         char temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (boolean[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         boolean temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (float[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         float temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}

   public static void shuffle (double[] array, int n, int k,
                               RandomStream stream)\begin{hide} {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt (i, n-1);
         double temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }\end{hide}
\end{code}
\begin{tabb} Similar to 
 \method{shuffle}{}{\texttt{(Object[], n, k, RandomStream)}}.
\end{tabb}
\begin{htmlonly}
   \param{array}{the array being shuffled.}
   \param{n}{selection amongst the first n elements.}
   \param{k}{number of elements selected.}
   \param{stream}{the random stream used to generate random numbers.}
\end{htmlonly}
\begin{code}\begin{hide}
}\end{hide}
\end{code}
